package com.example.lcode.backtrack;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

public class Question93 {

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s.length() == 0) {
            return res;
        }
        int length = 1;
        for (int i = 0; i < s.length(); i++) {
            StringBuilder target = new StringBuilder(s.substring(0, i + 1));
            restoreIpAddresses(res, s, target, i, length, 1, s.substring(0, i + 1));
        }
        return res;
    }

    private void restoreIpAddresses(List<String> res, String s, StringBuilder target, int startIndex ,int length, int number, String appendStr) {
        if (check(appendStr)) {
            startIndex = startIndex + 1;
            if (number < 4) {
                if (startIndex > s.length() - 1) {
                    return;
                }
            }
            if (number == 4 && target.length() - 3 == s.length()) {
                res.add(target.toString());
                return;
            } else if (number == 4 && target.length() - 3 != s.length()){
                return;
            } else if (number > 4) {
                return;
            }
        } else {
            return;
        }
        target.append(".");
        number ++;
        for (int i = startIndex; i < s.length(); i++) {
            target.append(s.substring(startIndex, i + 1));
            restoreIpAddresses(res, s, target, i , length + (i - startIndex + 1), number, s.substring(startIndex, i + 1));
            target.delete(target.length() - (i - startIndex + 1) , target.length());
        }
        number --;
        target.deleteCharAt(target.length() - 1);
    }

    boolean check(String appendStr) {
        int length = appendStr.length();
        String firstWord = String.valueOf(appendStr.charAt(0));
        if (length != 1 && firstWord.equals("0") || new BigDecimal(appendStr).compareTo(new BigDecimal(255)) > 0 ) {
            return false;
        }
        return true;
    }


    public static void main(String[] args) {
        Question93 question93 = new Question93();
        List<String> list = question93.restoreIpAddresses("0000");
        System.out.println(list);
    }

}
